package com.mlh.array;

// 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
// 输入：nums = [-4,-1,0,3,10]
// 输出：[0,1,9,16,100]
// 解释：平方后，数组变为 [16,1,0,9,100]
// 排序后，数组变为 [0,1,9,16,100]

//该题受限于边界条件的处理，没有写出来，对for和while结构特性没有较好的把握
public class SortedSquares {

    //寻找正负边界  然后利用类似于归并算法 对负数和正数不断进行对比 输入到结果数组中
    public int[] method1(int[] nums) {
        //需考虑
        //全为负数
        //全为正数
        //长度为1
        if(nums.length<=1){
            return new int[]{nums[0]*nums[0]};
        }
        int n=nums.length;
        int neg=-1;
        int[]res=new int[nums.length];
        //寻找正负边界
        for(int i=0;i<nums.length;i++){
           if(nums[i]<0){
               neg=i;
           }
        }
        int notNeg=neg+1;
        int index=0;
        while(neg>=0||notNeg<n){
            if(neg<0){
                res[index]=nums[notNeg]*nums[notNeg];
                index++;
                notNeg++;
            }else if(notNeg==n){
                res[index]=nums[neg]*nums[neg];
                index++;
                neg--;
            }else if(nums[neg]*nums[neg]>nums[notNeg]*nums[notNeg]){
                res[index]=nums[notNeg]*nums[notNeg];
                index++;
                notNeg++;
            }else{
                res[index]=nums[neg]*nums[neg];
                index++;
                neg--;
            }
        }
        return res;
    }

    //采用双指针方法
    //双指针法可以规避掉很多边界条件  例如全负数 全正数 数组长度为1 等等情况
    //因此代码比较简洁,也更好实现
    public int[] method2(int[] nums) {
        int n=nums.length;
        int head=0;
        int tail=n-1;
        int[]res=new int[n];
        int index=n-1;
        while (head<=tail){
            if(nums[head]*nums[head]>nums[tail]*nums[tail]){
                res[index]=nums[head]*nums[head];
                index--;
                head++;
            }else{
                res[index]=nums[tail]*nums[tail];
                index--;
                tail--;
            }
        }
        return res;
    }
}
